Many measurement techniques produce data representing the variation of some physical property over a three-dimensional volume. For example, magnetic imaging techniques used in medical imaging generate data representing the density and environment of hydrogen nuclei at various locations in the subject's body. Similarly, CAT scans measure the x-ray absorbance at various locations in the subject's body. All of these techniques generate three-dimensional arrays of data in which each point in the array represents the measured physical property at a corresponding point in the object under examination.
Presenting the large amount of data generated by such imaging techniques in a manner that is easily assimilated by human observers presents significant computational problems. The process of convening three-dimensional arrays of data to images representing that data is referred to as volume rendering. Several approaches to this problem have been implemented. In general, these approaches assign "optical" properties to each point in a three-dimensional volume which is broken into small volumes referred to as vowels. Ideally, an image is then produced by calculating the image one would see on a screen located between the object and the viewer if a three-dimensional object having these optical properties were viewed from a given location when the object is illuminated. Unfortunately, the computational difficulty inherent in taking into account reflections, absorption, and scattering in each voxel are too great to allow an exact computation to be made. Hence, various approximations to the exact computation are utilized.
One general approach which is computationally manageable is referred to as ray casting. This approach assigns color and opacity values to each voxel. A ray is generated corresponding to each pixel on the viewing screen. As the ray passes through the various voxels, color values are integrated along the ray path. The resultant calculated value is essentially equivalent to the light reaching the screen along the ray that would be generated if each voxel consisted of a material which generated light of the color in question and absorbed light according to the assigned opacity value. High opacity values at a particular voxel will cause a strong color contribution from that voxel as well as attenuating color values generated by voxels behind the voxel in question. The contributions of secondary rays produced by reflections and refractions in other voxels are ignored in this approximation.
While this type of volume rendering generates useful images, the computational workload is prohibitive if the three-dimensional data array is large. As the resolution of the measuring devices increases, the size of the three-dimensional data arrays in question increase dramatically. An improvement of a factor of two in resolution results in a factor of eight increase in the size of the three-dimensional data array and a similar increase in the computational workload.
On conventional sequential computers, the time to calculate a single view of the data may be several hours. Such long computational times severely limit the usefulness of such imaging techniques. In general, the viewer must examine several such images to find the view point that best displays the features of the data which are of interest. Hence, interactive systems in which the user can move his or her viewpoint relative to the "object" are advantageous. To provide such interactive displays, parallel computer computation is necessary.
In parallel computing systems, the computations are divided between a number of processors. Each processor is responsible for computing a portion of the image. Ideally, N processors should be able to produce an image in 1/N.sup.th the time needed for a single processor to generate the image. However, in practice, such improvements are seldom realized.
In prior art systems, the three-dimensional data array is stored in a memory which is accessed by each of the processors. The number of processors that can share the memory is limited by the bandwidth of the communication path connecting the memory to the processors. This path is shared by the various processors. Hence, there is a limit to the number of processors that can effectively operate on the data array. This limit is independent of the size of the memory array. Hence, as the size of the array increases with improvements in resolution of the measuring instruments, the gains obtained from parallel processing are reduced.
A second problem with this prior art approach is the complexity of the individual processors. Even if the effective memory bandwidth is increased, the cost of providing a large number of general purpose processors becomes a limiting factor in constructing an economically feasible system. Hence, an imaging system in which a substantial fraction of the computations can be performed by small special purpose processors is highly desirable.
Broadly, it is an object of the present invention to provide an improved imaging method and apparatus for performing volume rendering.
It is a further object of the present invention to provide an imaging method and apparatus which is not limited by the bandwidth of the memory in which the three-dimensional data array is stored.
It is yet another object of the present invention to provide an imaging method and apparatus which utilizes small inexpensive processors for a substantial portion of the computations.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the present invention and the accompanying drawings.